Unique Paths to Goal

Constraints:

• m $==$ matrix.length

• n $==$ matrix[i].length

• matrix[i][j] is either 1 or 0

• $1$ $\leq$ m, n $\leq 450$

Example#

Try it yourself#

Implement your solution in the following playground.

Note: If you clicked the "Submit" button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Recursive Number pattern.

Naive approach#

A naive approach is to find all the possible unique paths by traversing the array from start to finish. Every time, we need to check if we have reached the bottom-right corner of the matrix or if the iterating index exceeds the size of the matrix. If this condition is satisfied, we just stop the iteration here. If an obstacle is present in the array, the number of unique paths will be 0 up to that obstacle. After that, we will traverse to the next cell in the row and the column finding all the possible unique paths.

For example, we have the following matrix:

• Matrix: [ [0, 0], [1, 0] ]

We will use the recursive approach to find the unique number of paths up to the bottom-right corner of the matrix. For this, we will try all the possible paths and get only one solution which is moving right and then bottom to reach the bottom-right corner.

• Number of Unique Paths: 1

Let’s implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, enhances the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In this algorithm, we will create a 2-D array in which each cell will contain all the possible unique paths to reach itself. So when computing the unique paths to the next cell, we will use the stored values of the previous cell instead of computing them again. The value in the finish cell will be the number of unique paths to that cell.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. Here we again create a 2-D array of the same size as the matrix given. In the bottom-up approach, we start moving through the rows and filling in the values. If an obstacle (1) is found at any place, we will set the value of that cell to 0 because we cannot reach that place, so unique paths will be 0. Starting with the base condition, we will set the values of the first row and column to 1 if no obstacles are found. Now we will start traversing row-wise, if there is no obstacle, then the answer will be the sum of the values of the top and left cells, and if there is an obstacle, we will just insert the value 0 to that cell irrespective of the values of other cells.

Let’s look at the following illustration to get a better understanding of the solution:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.